package code.notdo;

import com.sun.xml.internal.ws.server.ServerRtException;

import java.util.*;

/**
 * author : yeswater
 * date : 2023/12/12
 * <p>
 * 最小覆盖子串
 * <p>
 * s 中涵盖 t 所有字符的最小子串 ,t 中重复的字符数量也要包含
 */

public class T076 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }

    /**
     * 自己写的啥???
     */
    public static String minWindow1(String s, String t) {
        int[] arr = {0, 0};
        int len = Integer.MAX_VALUE;
        int start = -1;
        int m = s.length();
        int n = t.length();
        if (m < n) {
            return "";
        }
        String replace = t;
        for (int i = 0; i < m; i++) {
            if (replace.equals("")) { // 全部包含
                replace = t;
                if (i - start < len) {
                    len = i - start;
                    arr[0] = start;
                    arr[1] = i - 1;
                    start = i;
                }

            } else {
                replace = replace.replace(String.valueOf(s.charAt(i)), "");
            }
        }
        if (replace.equals("")) {
            arr[0] = start;
            arr[1] = m;
        }
        if (len > 0) {
            return s.substring(arr[0], arr[1]);
        }
        return "";
    }

    /**
     * 没搞懂
     */
    public static String minWindow(String s, String t) {
        //维护s串中滑动窗口中各个字符出现次数
        Map<Character, Integer> hs = new HashMap<>();
        //维护t串中各个字符出现次数
        Map<Character, Integer> ht = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0)+1);
        }
        String ans="";
        //cnt维护s串[left,right]中满足t串的元素的个数，记录相对应字符的总数
        int len=Integer.MAX_VALUE,cnt=0;
        //区间[left,right]表示当前滑动窗口
        for (int left=0,right = 0; right < s.length(); right++) {
            hs.put(s.charAt(right), hs.getOrDefault(s.charAt(right), 0)+1);
            //如果ht表中也包含当前字符
            if (ht.containsKey(s.charAt(right))) {
                //并且hs表中的字符个数<=ht表中的字符个数,说明该字符是必须的，并且还未到达字符串t所要求的数量
                if (hs.get(s.charAt(right))<=ht.get(s.charAt(right))) {
                    cnt++;
                }
            }
            //收缩滑动窗口
            //如果左边界的值不在ht表中 或者 它在hs表中的出现次数多于ht表中的出现次数
            while(left < right && (!ht.containsKey(s.charAt(left)) || hs.get(s.charAt(left)) > ht.get(s.charAt(left)))){
                hs.put(s.charAt(left),hs.get(s.charAt(left)) - 1);
                left++;
            }
            //此时滑动窗口包含符串 t 的全部字符
            if (cnt==t.length()&&right-left+1<len) {
                len=right-left+1;
                ans=s.substring(left,right+1);
            }
        }
        return ans;
    }
}
